#include "Sorting.h"
#include<ctime>
template<typename Comparable>
void printvector(vector<Comparable> & vec)
{
    for(auto &x:vec)
    {
        cout << x << " ";
    }
}
template<typename Comparable>
void test(vector<Comparable> & vec)///测试函数，测定在不同百分率有序前提下的排序效率
{
    clock_t begin;
    clock_t end;

	/*random_shuffle(vec.begin()+1/100*vec.size(), vec.end());///百分之1%有序
    begin=clock();
    heapsort(vec);
    end=clock();
    cout<<"1%有序，堆排序消耗时间为： "<<double((end-begin))/CLOCKS_PER_SEC<<"s"<<endl;*/
    random_shuffle(vec.begin()+1/100*vec.size(),vec.end());
    begin=clock();
    quicksort(vec);
    end=clock();
    cout<<"1%有序，快速序消耗时间为： "<<double((end-begin))/CLOCKS_PER_SEC<<"s"<<endl;

    /*random_shuffle(vec.begin()+1/10*vec.size(), vec.end());///百分之10%有序
    begin=clock();
    heapsort(vec);
    end=clock();
    cout<<"10%有序，堆排序消耗时间为： "<<double((end-begin))/CLOCKS_PER_SEC<<"s"<<endl;*/
    random_shuffle(vec.begin()+0.9*vec.size(),vec.end());
    begin=clock();
    quicksort(vec);
    end=clock();
    cout<<"10%有序，快速序消耗时间为： "<<double((end-begin))/CLOCKS_PER_SEC<<"s"<<endl;

    /*random_shuffle(vec.begin()+0.9*vec.size(), vec.end());///百分之90%有序
    begin=clock();
    heapsort(vec);
    end=clock();
    cout<<"90%有序，堆排序消耗时间为： "<<double((end-begin))/CLOCKS_PER_SEC<<"s"<<endl;*/
    random_shuffle(vec.begin()+0.9*vec.size(),vec.end());
    begin=clock();
    quicksort(vec);
    end=clock();
    cout<<"90%有序，快速序消耗时间为： "<<double((end-begin))/CLOCKS_PER_SEC<<"s"<<endl;

    /*random_shuffle(vec.begin()+0.99*vec.size(), vec.end());///百分之99%有序
    begin=clock();
    heapsort(vec);
    end=clock();
    cout<<"99%有序，堆排序消耗时间为： "<<double((end-begin))/CLOCKS_PER_SEC<<"s"<<endl;*/
    random_shuffle(vec.begin()+0.99*vec.size(),vec.end());
    begin=clock();
    quicksort(vec);
    end=clock();
    cout<<"99%有序，快速序消耗时间为： "<<double((end-begin))/CLOCKS_PER_SEC<<"s"<<endl;


}
int main()
{
    vector<int> a;
    for(int i=0;i<500000;i++)
    {
        a.push_back(i);
    }
    test(a);
}